class Graph<T> {
  //顶点
  private vertexes: T[] = [];

  //边，邻接表
  private adjList: Map<T, T[]> = new Map();

  /* 添加顶点和边的方法 */
  addVertex(vertex: T) {
    this.vertexes.push(vertex);
    this.adjList.set(vertex, []);
  }

  addEdge(vertex1: T, vertex2: T) {
    this.adjList.get(vertex1)?.push(vertex2);
    this.adjList.get(vertex2)?.push(vertex1);
  }

  traverse() {
    console.log("Graph");
    this.vertexes.map(v => {
      const edges = this.adjList.get(v);
      console.log(`${v} -> ${edges?.join(" ")}`);
    });
  }

  //广度优先
  bfs() {
    //1.判断是否有节点
    if (!this.vertexes.length) return;

    //创建队列结构访问每一个顶点
    const queue: T[] = [];
    queue.push(this.vertexes[0]);

    //创建set结构，记录某一个顶点是否被访问过
    const visited = new Set<T>();
    visited.add(this.vertexes[0]);

    //遍历队列中每一个顶点
    while (queue.length) {
      //访问队列中第一个顶点
      const vertex = queue.shift()!;
      console.log(vertex);
      const neighbors: T[] | undefined = this.adjList.get(vertex);
      if (!neighbors) return;
      for (let neigh of neighbors) {
        if (!visited.has(neigh)) {
          visited.add(neigh);
          queue.push(neigh);
        }
      }
    }
  }

  //深度优先
  dfs() {
    //判断是否有顶点
    if (!this.vertexes.length) return;

    //创建栈结构
    const stack: T[] = [];
    stack.push(this.vertexes[0]);

    //创建set结构
    const visited = new Set<T>();
    visited.add(this.vertexes[0]);

    while (stack.length) {
      const vertex = stack.pop()!;
      console.log(vertex);
      const neighbors = this.adjList.get(vertex);
      if (!neighbors) continue;
      for (let i = neighbors?.length - 1; i >= 0; i--) {
        const nei = neighbors[i];
        if (!visited.has(nei)) {
          visited.add(nei);
          stack.push(nei);
        }
      }
    }
  }
}

const graph = new Graph<string>();

for (let i = 65; i < 74; i++) {
  graph.addVertex(String.fromCharCode(i));
}

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("C", "D");
graph.addEdge("C", "G");
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("E", "I");

graph.traverse();
// graph.bfs();
graph.dfs();

export {};
